/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：乘积最大子序列</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/maximum-product-subarray/
 * </pre>
 * <p>创建日期：2019年11月27日下午2:17:37</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code152MaximumProductSubarray</p>
 * 查看帮助：<a href="" target="_blank"></a> 
 *
 * 作者：yinjun
 * 初审：
 * 复审：
 * @version 1.0
 */
public class Code152MaximumProductSubarray
{
	public static void main(String[] args)
	{
		/**
		 * 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

		示例 1:

		输入: [2,3,-2,4]
		输出: 6
		解释: 子数组 [2,3] 有最大乘积 6。
		示例 2:

		输入: [-2,0,-1]
		输出: 0
		解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

		 */
		int maxProduct = maxProduct02(new int[] { 1, 1, 1, 1, 1, -3, 3, 3, 3 });
		System.out.println(maxProduct);
	}

	/**
	 * 本题采用动态规划思路:
	 * 		记数组nums
	 * 		记结果最大值result
	 * 		记数组中的每个序列S(i)的最大乘积值max
	 * 		则序列S(i+1)的乘积最大值有：
	 * 			max = Math.max(max*nums[i+1],nums[i+1])
	 * 		考虑各种情况：
	 * 			由于有负数存在的情况，导致最大的正数乘以一个负数变成了最小的，但是后续如果再乘以负数，又变成最大的
	 * 			所以在每次记住最大值max时,需要记住最小值min,以免在遇到下一个数时，大小颠倒
	 * 			min =  Math.min(min*nums[i+1],nums[i+1])
	 * 			如果遇到一个负数时，则:
	 * 							max=Math.max(min*nums[i+1],nums[i+1])
	 * 							min=Math.min(max*nums[i+1],nums[i+1])
	 * 
	 * 
	 * 时间复杂度：O(n)
	 * 空间复杂度：O(1)
	 * 
	 * @param nums
	 * @return
	 */
	public static int maxProduct02(int[] nums)
	{
		int min = nums[0];
		int max = nums[0];
		int result = nums[0];
		for (int i = 1; i < nums.length; i++)
		{
			//2, 3, -2, 4
			//为何要记录最小最大值，因为最大值可能再乘一个数就变成最小值，最小值再乘一个数就变成最大值
			//这里相当于遇到了负数的话，就交换max和min的值
			int _min = Math.min(max * nums[i], Math.min(min * nums[i], nums[i]));
			int _max = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));
			min = _min;
			max = _max;
			result = Math.max(result, max);
			System.out.println("min:" + min + "=======max:" + max + "======result:" + result);
		}
		return result;
	}

	/**
	 * 时间复杂度：O(n^2)
	 * @param nums
	 * @return
	 */
	public static int maxProduct(int[] nums)
	{
		//-2,3,2,0
		int max = nums[0];
		for (int i = 1; i < nums.length; i++)
		{
			int maxVal = nums[i];
			int temp = nums[i];
			for (int j = i - 1; j >= 0; j--)
			{
				temp = temp * nums[j];
				if (temp > maxVal)
				{
					maxVal = temp;
				} else
				{
					maxVal = nums[j] > maxVal ? nums[j] : maxVal;
				}
			}
			max = maxVal > max ? maxVal : max;
		}
		return max;
	}
}
